[BZOJ1041]HAOI2008圆上的整点

发表于 | 分类于 | | 阅读次数:

题目

题目描述

求一个给定的圆($x^2+y^2=r^2$)，在圆周上有多少个点的坐标是整数。

输入格式

r

输出格式

整点个数

样例输入

1
4

样例输出

1
4

说明

$n\le2000000000$

题解

转自这篇文章
这里先只考虑x，y都大于0的情况

如果$x^2+y^2=r^2$，则$(r-x)(r+x)=y^2$

令$d=gcd(r-x,r+x)$

则$(r-x)/d$与$(r+x)/d$一定互质，二者相乘为完全平方数，则二者一定都为完全平方数

令$r-x=d\times a^2$,$r+x=d\times b^2$

则显然有a,b互质，a<b

其中$$x=\frac{d(b^2-a^2)}{2}$$
$$y=d\times a\times b$$
$$r=\frac{d\times (a^2+b^2)}{2}$$

枚举$2r$的因数$d$，对于每个d我们用$O(\sqrt{\frac{r}{d}})$的时间枚举$a$ 代入$r$的计算式得出$b^2$ 计算$b^2$是否为完全平方数及$a^2$与$b^2$是否互质

这样可以枚举出一个象限内的整点个数 然后输出$(ans+1)\times 4$即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll r,ans;

ll gcd(ll a,ll b){
	return b? gcd(b,a%b):a;
}

void solve(ll x){
	ll top=(ll)sqrt(x/2);
	for(int a=1;a<=top;a++){
		ll A=a*a;
		ll B=x-A;
		ll b=(ll)sqrt(B);
		if(gcd(A,B)==1&&B==b*b&&A!=B){
			ans++;
		}
	}
}

int main(){
	cin>>r;
	ll top=(ll)sqrt(2*r);
	for(int i=1;i<=top;i++){
		if(2*r%i==0){
			solve(i);
			solve(2*r/i);
		}
	}
	cout<<ans*4+4;//+4个坐标轴上的点
	return 0;
}

附

这题还有一个更美妙的解法，0msAC，具体就是下面这个视频
如果你不想花时间看的话也可以看这篇文章，基本上就是整个视频对我们有用的知识的提炼

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long r;
    int ans=1;
    cin>>r;
    for(int i=2;i<=sqrt(r);i++){
        int p=0;
        while(r%i==0){
            if(i%4!=3){
                p+=2;
            }
            r/=i;
        }
        if(i!=2)
            ans*=(p+1);
    }
    if(r!=1){
        if(r%4!=3){
            ans*=3;
        }
    }
    cout<<ans*4<<endl;
    return 0;
}